﻿namespace Graph;

//求最小生成树
//思想：贪心法，按权值从小到大依次加入V-1条边（成环弃之）
public class Kruskal 
{
    private IGraph G;

    public MyList<Edge> ResultList { get; } = new MyList<Edge>();

    public Kruskal(IGraph G)
    {
        this.G = G;

        //确保联通图
        DFSConnectComponet cc = new DFSConnectComponet(G);
        if (cc.ComponentCount > 1)
        {
            return; 
        }

        MyList<Edge> edges = new MyList<Edge>();
        for (int a = 0; a < G.V; a++)
        {
            foreach (int b in G.Adj(a))
            {
                if (a < b) //只添加一条边，不能重复加边。
                {
                    edges.Add(new Edge(a, b, ((AdjDictionary)G).GetWeight(a, b)));
                }
            }
        }
        edges.Sort(); //Edge类实现IComparable<Edge>，确保edges可以排序。

        IUF uf = new UnionFindForest(G.V); //使用并查树进行动态环检测，选剩仅V-1条边。
        foreach (Edge edge in edges)
        {
            int a = edge.A;
            int b = edge.B;

            if (!uf.IsConnected(a, b)) //若待选边的两个端点同属一颗并查树，则构成环。
            {
                ResultList.Add(edge); //不成环，选边。
                uf.Union(a, b); //然后把树a合并到树b，已选相邻边各顶点同属一颗树。    
            }
        }
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjDictionary("带权图/g.txt");        

        Kruskal kruskal = new(graph);
        Console.WriteLine(kruskal.ResultList);
        Console.WriteLine(graph.V);
        Console.WriteLine(kruskal.ResultList.Count);        

        Console.Read();
    }
}
